#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN = 1e9 + 10;

int ch[MAXN];
priority_queue<int, vector<int>, greater<int>> q;

void huffmanEncode() {
    // 当队列中只剩下一个元素时，说明已经构建好了哈夫曼树
    while(q.size() > 1) {
        int a = q.top(); q.pop();
        int b = q.top(); q.pop();
        q.push(a+b);
    }
}

int main() {
    freopen("article.txt", "r", stdin);
    freopen("encode.txt", "w", stdout);
    int id = 0, c;
    int cnt[256];
    memset(cnt, 0, sizeof(cnt));

    // 读入文章
    while((c=getchar())!=EOF && id<MAXN)
        ch[id++] = c;

    // 统计每个字符出现的次数
    for(int i=0; i<id; i++)
        cnt[ch[i]]++;

    // 把出现次数大于0的字符的出现次数加入优先队列
    for(int i=0; i<256; i++)
        if(cnt[i] > 0)
            q.push(cnt[i]);
    
    huffmanEncode();
    
    return 0;
} 